package b_sort.a_3_insertion_sort;

import static b_sort.StringUtils.printArr;

/**
 * 插入排序
 * 时间复杂度    O(n) | O(n^2) | O(n^2)
 * 空间复杂度    O(1)
 * 稳定性       稳定
 * ------
 * 思路：构建有序序列，对于未排序的，在有序序列中从后往前扫描，找到对应位置插入
 * 外层 FOR 表明未排序元素个数，每个元素都需要进行扫描插入，默认第一个元素有序
 * 内层 FOR 从后往前扫描插入位置，若前一个元素比自己小，则插入当前位置
 *
 * @author FRSF
 * @since 2025/2/27 22:20
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {3, 8, 1, 5, 10, 6, 7, 2, 9, 4};
        insertionSort(arr);
    }

    private static void insertionSort(int[] arr) {
        printArr(arr);
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j--];
            }
            arr[j+1] = key;
        }
        printArr(arr);
    }
}
